package com.xj.algorithm.leetcode;

import java.util.Arrays;
/**
 * 最小移动次数使数组元素相等
 */
public class L453_最小移动次数使数组元素相等 {

    /**
     * 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
     *
     * 示例:
     *
     * 输入:
     * [1,2,3]
     *
     * 输出:
     * 3
     *
     * 解释:
     * 只需要3次移动（注意每次移动会增加两个元素的值）：
     *
     * [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
     *
     * 注意：我们不考虑数组的移动方式，我们只直到每次操作，让n-1个数加1
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        System.out.println(minMoves(nums));

        int[] nums2 = new int[]{1,1,1};
        System.out.println(minMoves(nums2));

        int[] nums3 = new int[]{1,2147483647};
        System.out.println(minMoves(nums3));

        int[] nums4 = new int[]{1,2147483647};
        System.out.println(minMovesOffice(nums4));
    }

    //自己的解法：找最值，比较每个值和最小值的差，然后累加求和等于移动次数
    public static int minMoves(int[] nums) {
        int length=nums.length;
        int min=nums[0];
        for (int i=0;i<length;i++){
            if(min>nums[i]){
                min=nums[i];
            }
        }

        int count=0;
        for (int i=0;i<length;i++){
            if(nums[i]>min){
                count=count+nums[i]-min;
            }
        }
        return count;
    }


    //官方的解法：排序然后减法累加
    public static int minMovesOffice(int[] nums) {
        Arrays.sort(nums);  //默认从小到大排序
        int count = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            count += nums[i] - nums[0];
        }
        return count;
    }

}
